package puzzle.projecteuler.p300;

import astudy.util.AdvMath;

public class Problem249C {

	/**
	 * Compare with Problem 250
	 * 
	 * anwser	: 9275262564250418
	 * time cost: 138203 ms
	 * @param args
	 */
	public static void main(String[] args) {
		
		long start = System.currentTimeMillis();
		
		Integer[] primes = AdvMath.primes(5000);
		int sum = 0;
		for (Integer a: primes) {
			sum += a;
		}
		
		//calculate number of subsets
		long n10_16 = 10000000000000000L;
		long[] A = new long[sum+1];	//A[i] = |{T | T is a subset of primes and S(T) = j}|
		for (int i = 0; i < A.length; i ++) {
			A[i] = 0L;
		}
		long[] B = new long[sum+1];
		for (int i = 0; i < primes.length; i ++) {
			for (int j = 0; j < A.length; j ++) {
				B[j] = A[j];
			}
			//递推
			int n = primes[i];
			for (int j = 0; j < A.length; j ++) {
				A[j] = B[j];
				if (j > n) {
					A[j] += B[j-n];
				} else if (j == n) {
					A[j] += 1;
				}
				A[j] %= n10_16;
			}
		}
		
		long count = 0;
		Integer[] primeSums = AdvMath.primes(sum);	//可能作为子集和的素数
		for (Integer p: primeSums) {
			count += A[p];
			count %= n10_16;
		}
		System.out.println(count);
		System.out.println((System.currentTimeMillis()-start) + " ms");
	}
}
